Compromise Solutions for Robust Combinatorial Optimization with Variable-Sized Uncertainty

摘要

In classic robust optimization, it is assumed that a set of possibleparameter realizations, the uncertainty set, is modeled in a previous step andpart of the input. As recent work has shown, finding the most suitableuncertainty set is in itself already a difficult task. We consider robustproblems where the uncertainty set is not completely defined. Only the shape isknown, but not its size. Such a setting is known as variable-sized uncertainty. In this work we present an approach how to find a single robust solution,that performs well on average over all possible uncertainty set sizes. Wedemonstrate that this approach can be solved efficiently for min-max robustoptimization, but is more involved in the case of min-max regret, wherepositive and negative complexity results for the selection problem, the minimumspanning tree problem, and the shortest path problem are provided. We introducean iterative solution procedure, and evaluate its performance in anexperimental comparison.